LeetCode——删除链表的倒数第N个节点

NO.19 删除链表的倒数第N个节点 中等

思路一：两次遍历 第一次遍历得到链表的长度L，第二次遍历删除第（L-N+1）个元素。

public ListNode removeNthFromEnd(ListNode head, int n) {
        int len=0;
//        依然是借助哑节点
        ListNode dummy=new ListNode(0),q=head;
        dummy.next=head;
//        第一次遍历获取链表长度
        while (q!=null){
            len++;
            q=q.next;
        }
//        第二次遍历找到待删除节点的前一个节点
        q=dummy;
        len-=n;
        while (len>0){
            len--;
            q=q.next;
        }
//        删除目标节点
        q.next=q.next.next;
        return dummy.next;
    }

操作执行了2L-n步，时间复杂度为O(L)。

思路二：快慢指针一次遍历 1. 用两个指针p、q分别指向链表的开头(哑节点)。2. 先让q指针逐步移动到距离p指针n+1的位置上，也就是上p指针和q指针间隔n个节点。3. 让p指针和q指针同时向后移动，直至q指针为null。4. 此时p指针指向的节点的下一个节点就是待删除节点，p.next=p.next.next删除即可。

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode p=dummy;
        ListNode q=dummy;
//        首先让q指针移动到和p指针间隔n个元素的位置
        for (int i=1;i<=n+1;i++){
            q=q.next;
        }
//        此时让p和q保持间距的情况下，同时向后移动，直到q为null
        while (q!=null){
            q=q.next;
            p=p.next;
        }
//        删除目标节点
        p.next=p.next.next;
        return dummy.next;
    }

操作执行了L+n+1步，时间复杂度为O(L)。

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github